#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>


class Solution {
public:
    vector<vector<string>> ret;
    int len;
    vector<string> path;
    vector<bool> check;
    vector<vector<string>> solveNQueens(int n) {
        len = n;
        check.resize(n + 1, true);
        dfs(0);
        return ret;
    }
    void dfs(int row)
    {
        if (len == row)
        {
            ret.push_back(path);
            return;
        }
        for (int i = 0; i < len; i++)
        {

            if (check[i])
            {
                int m = row - 1;
                int left = i - 1;
                int right = i + 1;
                int flag = 1;
                while (m >= 0)
                {
                    if (left >= 0 && path[m][left] == 'Q')
                    {
                        flag = 0;
                        break;
                    }
                    if (right < len && path[m][right] == 'Q')
                    {
                        flag = 0;
                        break;
                    }
                    left--;
                    right++;
                    m--;
                }
                if (flag == 0)
                    continue;
                string tmp;
                for (int j = 0; j < i; j++)
                {
                    tmp += '.';
                }
                tmp += 'Q';
                for (int j = i + 1; j < len; j++)
                {
                    tmp += '.';
                }
                path.push_back(tmp);
                check[i] = false;
                dfs(row + 1);
                path.pop_back();
                check[i] = true;
            }
        }
    }
};

int main()
{
    Solution s;
    s.solveNQueens(4);
    return 0;
}
//int ret;
//int end;
//vector<bool> check;
//vector<int> perm;
//vector<int> path;
//void dfs(int pos)
//{
//    if (path.size() == ::end)
//    {
//        ret++;
//        return;
//    }
//    for (int i = 1; i <= ::end; i++)
//    {
//        if (check[i])
//        {
//            if (i % (path.size() + 1) == 0 || (path.size() + 1) % i == 0)
//            {
//                path.push_back(i);
//                check[i] = false;
//                dfs(i + 1);
//                check[i] = true;
//                path.pop_back();
//            }
//        }
//    }
//}
//int countArrangement(int n) {
//    ret = 0;
//    ::end = n;
//    check.resize(n + 1, true);
//    dfs(1);
//    return ret;
//}


//int main()
//{
//    countArrangement(2);
//    return 0;
//}